/**
 * 快速排序
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */

const quickSort = (arr) => {
  if (arr.length < 2) return arr

  // 获取中间元素为基点
  const mid = ~~(arr.length / 2)
  const povid = arr.splice(mid, 1)

  // 创建两个数组保存小于基点和大于基点的元素
  const left = [], right = []

  for (let i = 0; i < arr.length; i++) {
    // 小于基点存进 left，否则存进right
    if (arr[i] < povid) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }

  // 递归进行排序
  return [...quickSort(right), ...povid, ...quickSort(left)]
}

const findKthLargest = (nums, k) => {
  nums = quickSort(nums)
  return nums[k - 1]
}

console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2))
// console.log(quickSort([3, 2, 1, 5, 6, 4, 7]))